package linear.linked.single.circle;

/**
 * 快慢指针-判断链表是否有环
 * 快慢指针-寻找链表的环的入口
 * @author caasi
 * @since 2022-01-17 15:43:43
 */
public class CircleQuestion{

    public static void main(String[] args) {
        CircleNode<String> first = new CircleNode<>("a", null);
        CircleNode<String> second = new CircleNode<>("b", null);
        CircleNode<String> third = new CircleNode<>("c", null);
        CircleNode<String> fourth = new CircleNode<>("d", null);
        CircleNode<String> fifth = new CircleNode<>("e", null);
        CircleNode<String> sixth = new CircleNode<>("f", null);
        CircleNode<String> seventh = new CircleNode<>("g", null);
        CircleNode<String> eighth = new CircleNode<>("h", null);
        
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = sixth;
        sixth.next = seventh;
        seventh.next = eighth;
        eighth.next = third;

        boolean flag = hasCircle(first);
        System.out.println(flag);
        CircleNode<String> entrance = getEntrance(first);
        System.out.println(entrance.value);
    }
    
    //链表是否有环
    public static boolean hasCircle(CircleNode<String> node) {
        CircleNode<String> fast = node;
        CircleNode<String> slow = node;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                return true;
        }
        return false;
    }
    
    //寻找环的入口
    public static CircleNode<String> getEntrance(CircleNode<String> node) {
        CircleNode<String> fast = node;
        CircleNode<String> slow = node;
        boolean flag = false;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                flag = true;
                break;
            }
        }
        if (flag) {
            CircleNode<String> temp = node;
            while (temp != slow) {
                temp = temp.next;
                slow = slow.next;
            }
            return temp;
        }
        return null;
    }
    
    private static class CircleNode<E>{
        private E value;
        private CircleNode<E> next;
        
        public CircleNode(E value, CircleNode<E> next){
            this.value = value;
            this.next = next;
        }
    }
    
    
}
